package com.cat.dataStructure03;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-palindromic-subsequences/description/
 * @create 2025/11/7 18:35
 * @since JDK17
 */

class Solution17 {
    static long N = (long) 1e9 + 7;
    public int countPalindromes(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        long ans = 0;
        int[] pre = new int[10], suf = new int[10];
        int[][] pre2 = new int[10][10], suf2 = new int[10][10];
        for (int i = n - 1; i >= 0; i--) {
            int x = arr[i] - '0';
            for (int j = 0; j < 10; j++) {
                suf2[x][j] += suf[j];
            }
            suf[x]++;
        }
        for (int i = 0; i < n; i++) {
            int x = arr[i] - '0';
            suf[x]--;
            for (int j = 0; j < 10; j++) {
                suf2[x][j] -= suf[j];
            }
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    ans += (long) pre2[j][k] * suf2[j][k];
                }
            }
            for (int j = 0; j < 10; j++) {
                pre2[x][j] += pre[j];
            }
            ++pre[x];
        }

        return (int) (ans % N);
    }
}